package leetcode_2401_2500;

import node.Node;
import node.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_2476 {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        System.out.println(closestNodes(new TreeNode(4, null, new TreeNode(9)), list));
    }
    private static List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<Integer> list = new ArrayList<>();
        f(root, list);
        List<List<Integer>> ans = new ArrayList<>();
        for (Integer query : queries) {
            List<Integer> son = new ArrayList<>();
            int i1 = smaller(list, query);
            son.add(i1 == -1 ? -1 : list.get(i1));
            int i2 = bigger(list, query);
            son.add(i2 == -1 ? -1 : list.get(i2));
            ans.add(son);
        }
        return ans;
    }
    private static int smaller(List<Integer> arr, int goal){
        int l = 0, r = arr.size() - 1;
        while (l < r){
            int m = (l + r + 1) >>> 1;
            if (arr.get(m) > goal){
                r = m - 1;
            }else {
                l = m;
            }
        }
        if(arr.get(l) > goal){
            return -1;
        }
        return l;
    }

    private static int bigger(List<Integer> arr, int goal){
        int l = 0, r = arr.size() - 1;
        while (l < r){
            int m = (l + r) >>> 1;
            if (arr.get(m) < goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        if(arr.get(l) < goal){
            return -1;
        }
        return l;
    }

    private static void f(TreeNode node, List<Integer> list){
        if (node == null)
            return;
        f(node.left, list);
        list.add(node.val);
        f(node.right, list);
    }
}
